In the design of integrated circuits, there is a tradeoff between competing design goals: area of the circuit, critical path delay (speed) of the circuit, testability of the circuit, and power consumption of the circuit. The rapidly growing complexity in very large scale integrated (VLSI) circuits and the sheer mass of detail in VLSI designs necessitates the use of automated synthesis tools in order to design an optimized circuit which balances all of these design constraints. Logic synthesis is described in Logic Synthesis and Verification Algorithms, by Gary D. Hachtel and Fabio Somenzi, and in Synthesis and Optimization of Digital Circuits, by Giovanni De Micheli, the disclosures of which are hereby incorporated by reference.
Automated design systems are used in converting logic designs to specific circuits in the production of application specific integrated circuits (ASICs). This typically involves mapping the logic design, called a "technology-independent circuit" (or network), into one or more logic gates in a pre-designed set of gates called a technology library. The resulting circuit may be variously called "technology-dependent", "technology-mapped", or simply "mapped".
The technology library depends on the manufacturer and the target technology selected. For example, target technologies might include CMOS (complementary metal-oxide-semiconductor), NMOS (n-type metal-oxide-semiconductor), PMOS (p-type metal-oxide-semiconductor), TTL (bipolar transistor-to-transistor logic), and ECL (emitter-coupled logic). Further differentiation among target technologies may be based on minimum feature size, resulting in, for example, a 0.25 micron CMOS technology, a 1.0 micron CMOS technology, and a 2.0 micron CMOS technology.
Initially, the logic design may be specified in the form of Boolean equations or an HDL (hardware description language) description in a language such as Verilog or VHDL (Very High Speed Integrated Circuits Hardware Description Language). The automated design system generates a technology-independent, unmapped network that is a directed graph where the vertices (nodes) represent logic gates and the edges represent the nets connecting the gate outputs to gate inputs. This technology-independent network is optimized and mapped, producing a technology-mapped network. Typically, some restructuring is performed in order to meet specified design criteria (delay times, area, etc.). This is generally a repetitive optimizing process that involves countless changes to the logic network, with many recalculations of various network parameters after each change. One such parameter is speed, which is related to the time required for a change in one of the inputs to travel through the network to produce a change in one of the outputs. Another parameter is area, which is generally related to the number of transistors required to implement a given design.
The task of technology mapping may typically be divided into two steps. In the first step, it is necessary to determine, at each node of the technology independent circuit, a set of groupings of nodes and edges having the node as the root. These groupings are called "candidate clusters". A check is then performed to determine whether each cluster is "realizable"; i.e., the cluster can be implemented by a cell from the technology library. A cluster is considered realizable if the cluster's function can be implemented by a cell in the library, either directly, or by inverting the inputs, permuting the inputs, or inverting the outputs (i.e. if the cluster's function is "NPN equivalent" to a cell in the library). Technology mapping using Boolean matching is described in Frederic Mailhot and Giovanni De Micheli, "Technology Mapping Using Boolean Matching and Don't Care Sets", Proceedings of the European Conference on Design Automation, p. 212-216 (1990), the disclosure of which is hereby incorporated by reference. In the second step, the realizable clusters are used to completely cover the technology-independent network. As stated above, this is done while attempting to meet design constraints while minimizing area to the extent possible.
Current automated design systems generally use some type of level constraint during the generation of candidate clusters. In other words, they extract from the technology-independent network all clusters which have a maximum length L with the node as the root. The length is defined as the longest path in the extracted network, and may be determined by counting the number of nodes from the root node to the end of the longest path. The maximum number of clusters that may thus be generated can be calculated exactly, and the recurrence relation is EQU n(L)=(n(L-1)+1)*(n(L-1)+1), and N(1)=1
For L=1, the number of clusters examined is 1. For L=2, the number of clusters examined is 4. For L=3, 4, and 5, the number of clusters examined is, respectively: 25, 676, 458329. Clearly, this computation rapidly becomes intractable for larger values of L.
Because of the explosion in the number of clusters to be examined, practical systems limit choice of L to small values. However, this reduces the number of realizable clusters found by the system at a given node. Furthermore, larger library cells are never used, because the candidate clusters generated by the system are of limited length. These limitations result in poor quality of technology mapping and inability to map to large cells, with suboptimal results.
The need exists, therefore, for more efficient candidate cluster generation for use in technology mapping.